1. Field of the Invention
The invention relates to the technical field of Viterbi decoding and, more particularly, to a method of Viterbi decoding with reduced butterfly operation.
2. Description of Related Art
Currently, in communication systems, the convolutional codes are widely used to increase the reliability of transmission due to their high error-correcting capability. In contrast to the block codes, the convolutional codes contain a high error-correcting capability by increasing their constraint length rather than increasing the code redundancy, and therefore require less transmission bandwidth to compensate the redundancy.
The Viterbi decoding method is the most popular decoding scheme of the convolutional codes. It finds the sequence of branch words closest in distance to the received noisy sequence in a trellis diagram. To find the closest sequence, the branch metric for each branch in the trellis diagram needs to be computed. A code with rate k/n and constraint length v has 2k+v branches at each decoding stage. Hence, the computational complexity of the Viterbi decoding method increases exponentially with constraint length v.
For rate 1/n convolutional codes, a butterfly operation has been used to simplify the implementation of the Viterbi decoding method by exploiting the symmetry of trellis branches. The butterfly contains a pair of origin and destination states, and four branches. Since the branch word in the butterfly is either the same or complement to the other, only one branch metric needs to be computed. Hence the branch metric computation can be reduced by a factor of 4. Unfortunately, the butterfly operation only works for rate 1/n convolutional codes.
A conventional 2/n convolutional encoder is shown in FIG. 1. As shown in FIG. 1, the encoder has two shift registers 11 and 12 with lengths v1+1 and v2+1 respectively, and its overall constraint length is defined as v=v1+v2. Two input bits u1 and u2 are shifted at a time and n output bits from the n adders yield the output word y1y2 . . . yn. The generator sequence of the i-th output bit yi with respect to the j-th input bit uj is denoted as gji=[gj,0i, gj,1i, . . . , gj,vji] where i=1, . . . , n and j=1, 2. The output bit yi can be written as the following equation (1):
                                                                                             y                  i                                =                                ⁢                                                                            g                                              1                        ,                        0                                            i                                        ·                                          u                      1                                                        ⊕                                                            g                                              1                        ,                        1                                            i                                        ·                                          s                                              1                        ,                        1                                                                              ⊕                  ⋯                  ⊕                                                            g                                              1                        ,                                                  v                          1                                                                    i                                        ·                                          s                                              1                        ,                                                  v                          1                                                                                                      ⊕                                                                                                                        ⁢                                                                                                    g                                                  2                          ,                          0                                                i                                            ·                                              u                        2                                                              ⊕                                                                  g                                                  2                          ,                          1                                                i                                            ·                                              s                                                  2                          ,                          1                                                                                      ⊕                    ⋯                    ⊕                                                                  g                                                  2                          ,                                                      v                            2                                                                          i                                            ·                                              s                                                  2                          ,                                                      v                            2                                                                                                                                ,                                                                                          (          1          )                    where ⊕ denotes the modulo-2 adder.
The trellis diagram is an alternative method of describing a convolutional code. In the trellis representation of a convolutional code, the state S is defined as the shift register content except input bits (u1, u2), and has a binary v-tuple form as shown in the following equation (2):S=(s1,1s1,2 . . . s1,v1s2,1s2,2 . . . s2,v2)  (2)
FIG. 2 shows a schematic view of the trellis of a rate 2/n convolutional code with 2v state nodes. The input bits u1u2 cause the state node S to make a state transition from the origin state node(s1,1s1,2 . . . s1,v1s2,2 . . . s2,v2) to the destination state node (u1s1,1s1,2 . . . s1,v1−1u2s2,1s2,2 . . . s2,v2−1). Each state node has four branches, each corresponding to one of four possible input values. Each trellis stage has total 2v+2 branches.
The Viterbi decoding method finds the sequence of branch words closest in distance to the received noisy sequence in the trellis diagram. To find global most-likely path, however, the Viterbi decoding method must compute the branch metric of 2v+2 branches in each decoding stage. The branch metric is the distance between the received symbol and the branch word. The hamming distance is applied for hard decision decoding method, while the Euclidean distance is applied for soft decision decoding method. Soft decision decoding method captures more information and consequently performs better than hard decision decoding method, but the soft decision decoding method has a higher computational complexity. The branch metrics accumulated along a path in the trellis diagram form a path metric. When four paths enter the same state, the path with the smallest path metric is selected as the surviving path. Once the traceback depth has been reached, the path with the smallest path metric is selected as the global most-likely path. Finally, the decoder performs a traceback procedure along the path that is most likely to generate the decoded output. Hence, the computational complexity of the Viterbi decoding method increases exponentially with constraint length v. Thus, the practical application of the Viterbi decoding method with a long constraint length is limited. Therefore, it is desirable to provide an improved method to mitigate and/or obviate the computational complexity problems of the Viterbi decoding method.